//这个代码首先说一下，并不完全按照书的代码来的，
//并且99%无法得到书中的结果，我写这些代码主要是为了理解
//代码是如何运行的，请勿盲目的学习


//代码的需求：这里通过一个例子来看分治算法的应用。一个袋子里有3 0个硬币，其中一枚是假币，并且假币 
//和真币一模-样，肉眼很难分辨，目前只知道假币比真币重量轻一点。请问如何区分出假币？

//代码如何实现：( 1 )首先为每个银币编号，然后将所有的银币等分为两份，放在天平的两边。这样就将区分 
// 3 0个硬币的问题，变为区别两堆硬币的问题。
// ( 2 )因为假银币的分景较轻，因此天平较轻的一侧中一定包含假银币。
// ( 3 )再将较轻的一侧中的硬银币等分为两份，重复上述的做法。
// ( 4 )直到剩下2 枚硬银币，可用天平直接找出假银币来。
// 这种方法在银币个数较多时有明显的优势。我们可以按照这个思路来编写相应的寻找假币问题

//      代码的个人思考：
//      方法就是分份，最终结果就是称两个，看谁轻就是假币。但是过程分割过程中，会出现奇数以及偶数的出现，如
//      30个硬币，分了两堆，一堆轻，再分的时候15个硬币怎么分？？以及最后迭代完后是什么情况
#include <iostream>
#include <map>
#include <string>
#include <algorithm>

using namespace std;
int FalseCoin(int coin[],int low,int high);

int FalseCoin(int coin[],int low,int high)
{
    int i, sum1,sum2,sum3;
    int re; //用于存储result
    sum1=sum2=sum3=0;
    //迭代到最后的比较是如何比较的
    if(low+1==high)
    {
        if(coin[low]<coin[high])
        {
            re=low+1;//因此从0开始迭代的
            return re;
        }
        else 
        {
            re=high+1;
            return re; //因为这个函数是int返回类型的函数，因此需要返回一个int类型的数值
        }
    }

    //首先先判断一下，是否是偶数个分
    if ((high-low+1)%2==0) 
    {
        for(i=0;i<=low+(high-low)/2;i++)
        {
            sum1=sum1+coin[i];
        }
        
        for(i=(low+(high-low)/2)+1;i<=high;i++) //注意+1这个操作，而且好像int是默认向下取整的
        {
            sum2=sum2+coin[i];
        }

        //判断两个天平谁大谁小
        if(sum1<sum2)
        {
            //嵌套在执行该函数
            re=FalseCoin(coin,low,low+(high-low)/2); //在这里其实就掉入到循环了
            return re;
        }
        if(sum1>sum2)
        {
            re=FalseCoin(coin,low+(high-low)/2,high);//在这里其实就掉入到循环了
            return re;
        }
        else
        {
            //这里可能是原作者的习惯吧
        }
    }
    else //这里就是奇数了，因此奇数不太可能好分，因此代码里面分了三份，除去了中间的。
    {
        for(i=0;i<=low+(high-low)/2-1;i++)
        {sum1=sum1+coin[i];}
        for(i<=low+(high-low)/2+1;i<high;i++)
        {sum2=sum2+coin[i];}
        sum3=coin[low+(high-low)/2];
        if(sum1<sum2)
        {
            //嵌套在执行该函数
            re=FalseCoin(coin,low,low+(high-low)/2);
            return re;
        }
        if(sum1>sum2)
        {
            re=FalseCoin(coin,low+(high-low)/2,high);
            return re;
        }
        else
        {
            return low+(high-low)/2;//其实这里和下面的注释的sum1+sum3判断的内容是重合的
        }
        // if(sum1+sum3==sum2+sum3)
        // {
        //     re=low+(high-low)/2+1;
        //     return re;
        // }
    }
    
}
int main()
{
    cout<<"test0"<<endl;
    int coin[]={1,1,1,1,1,1,0,1,1,1};
    int weizhi=FalseCoin(coin,0,10);//这里可以有升级空间，比如
    cout<<weizhi<<endl;
}